W4. Linear-Time Sorting

1. Theory

1.1 Lower Bound for Comparison-Based Sorting

One of the fundamental results in computer science is that comparison-based sorting algorithms cannot be faster than in the worst case. This is a mathematical barrier: no matter how clever your algorithm is, if it relies only on comparing elements, it must make at least comparisons.

1.1.1 Key Ideas About Sorting

Before proving the lower bound, let’s understand the landscape of sorting algorithms:

1. Quadratic sorts work fast on small arrays: Algorithms like insertion sort and selection sort run in time. While this seems slow, these algorithms have excellent constant factors due to efficient loops and processor cache usage. For very small arrays (typically ), insertion sort often beats sophisticated algorithms. This is why production sorting algorithms often use insertion sort on small subarrays.
2. Comparison-based sorts have a lower bound: In general, sorting cannot be faster than . This applies strictly to algorithms that make decisions based only on comparing elements (like “is ?”).
3. Special cases allow linear time: When we have additional information about the data (like knowing the range of values), we can sometimes sort faster than . This is the topic of this lecture: linear-time sorting algorithms.

1.1.2 The Decision Tree Model

To understand why comparison-based sorting requires comparisons, we use the decision tree formalism:

A decision tree is a binary tree that represents the execution of a comparison-based sorting algorithm:

• Internal nodes represent comparisons (e.g., “Is ?”). Each internal node has two child branches: one for the “true” outcome (left) and one for the “false” outcome (right).
• Leaves represent possible outcomes — different permutations of the input.
• Paths from root to leaf represent possible execution traces. Each path corresponds to a sequence of comparisons leading to a final sorted order.

Example: For sorting three elements , the decision tree shows:

• Root compares and
• Based on the outcome, further comparisons determine which of the permutations is correct
• Leaves are the six possible sorted orderings

The height of the decision tree corresponds to the worst-case number of comparisons — it is the longest path from root to any leaf.

For any sorting algorithm with input size :

• There must be at least different leaves (one for each possible input permutation that could result in a different sorted order)
• A complete binary tree of height has at most leaves
• Therefore: , which gives

1.1.3 Deriving the Lower Bound

We need to lower-bound :

To find a lower bound:

Conclusion: Any comparison-based sorting algorithm requires at least comparisons in the worst case.

1.2 Counting Sort

Counting Sort is a linear-time sorting algorithm that works when elements come from a small, known range of values. Instead of comparing elements, it counts occurrences of each value and reconstructs the sorted array.

1.2.1 Assumption and Basic Idea

Assumption: Elements are integers in the range for some parameter . If you have a large range of integers, you can sometimes normalize them to fit this assumption.

Main idea:

1. Count frequencies: Create an array where initially stores how many elements equal .
2. Compute cumulative counts: Transform into a cumulative array where now stores how many elements are . This tells us the final position of each element.
3. Place elements: Traverse the input array and place each element in its correct position based on the cumulative counts, decrementing counts to handle duplicates.

The advantage of using cumulative counts is that it preserves stability — equal elements maintain their original relative order.

1.2.2 Naive Variant (Not Stable)

The simplest version just counts and writes elements back:

1. Count occurrences: = number of elements equal to
2. Iterate through values to in order
3. Write copies of value to the output

This is time and stable-preserving by nature, but doesn’t use indices effectively.

1.2.3 Stable Variant with Cumulative Counts

For problems requiring stability or more sophisticated sorting:

1. Count frequencies: Let = count of elements equal to .
2. Cumulative sums: Let . Now = index where the last element with value should go.
3. Backward traversal: Traverse the input array from right to left. For each element with value at some position, place it at position in the output, then decrement .

Why backward traversal? Processing from right to left ensures that when we have multiple elements with the same value, they are placed in the output in their original relative order.

Example: Input with values in range .

• Count: (two 0s, zero 1s, two 2s, three 3s, etc.)
• Cumulative:
• Process from right to left:
  • Element 3 at index 7 goes to position ; set
  • Element 0 at index 6 goes to position ; set
  • … and so on
• Output:

1.2.4 Time and Space Complexity

• Time:
  • Counting:
  • Cumulative sum:
  • Placement:
  • Total:
• Space: for the output array and count array

When is counting sort practical? When is small relative to . If , it’s competitive with algorithms. If , it’s worse than merge sort.

1.3 Radix Sort

Radix Sort extends the idea of counting sort to handle multi-digit numbers. It sorts numbers digit-by-digit, starting from the least significant digit (rightmost) and proceeding to the most significant digit (leftmost). The key insight is that if you have already sorted by more significant digits, sorting by less significant digits won’t disturb that order, as long as you use a stable sort.

1.3.1 Problem Setup

Input: Numbers with digits, where each digit is in the range .

Idea: Sort the numbers times:

1. Sort by digit (least significant)
2. Sort by digit (stable)
3. …
4. Sort by digit (most significant, stable)

After these passes, the numbers are fully sorted.

1.3.2 Why It Works

Claim: After sorting by the last digits, numbers are sorted by those digits.

Proof sketch:

• Initially (after sorting by the last digit): numbers with the same digits through may appear in any order relative to each other, but all numbers with a smaller last digit come before those with a larger last digit.
• After sorting by digits and (using a stable sort at each step): the most significant positions are correct, and the stable sort preserves the relative order of numbers equal on the current digit.

Example: Sorting (3-digit numbers, each digit in ).

1. Sort by digit 1 (units): (by last digit: 0, 5, 6, 7, 7, 9, 9; note stability)
2. Sort by digit 2 (tens, stable): (by middle digit: 2, 2, 3, 3, 5, 5, 5)
3. Sort by digit 3 (hundreds, stable): (by first digit: 3, 3, 4, 4, 6, 7, 8)

Result: Fully sorted!

1.3.3 Time Complexity

If we use counting sort to sort by each digit:

• Each of the passes uses counting sort with elements and possible digit values.
• Time per pass:
• Total time:

Special case — sorting -bit binary numbers:

• Each number has bits (digits in base 2, so ).
• Time:
• For numbers in range :

We can optimize further by using larger “digits” (processing multiple bits at a time). If we process -bit chunks, we have passes and possible values per digit:

The optimal choice is , giving time for sorting -bit numbers when or for reasonably-sized numbers.

1.4 Bucket Sort

Bucket Sort is another linear-time algorithm that works when elements are uniformly distributed in a known range (typically ). It divides the range into buckets, distributes elements into buckets, sorts within buckets, and concatenates.

1.4.1 Assumption and Basic Idea

Assumption: Input consists of numbers uniformly distributed in the interval . We can generalize to any interval by rescaling.

Algorithm:

1. Create buckets — divide the range into equal intervals: , , …, .
2. Distribute elements — for each element , place it in bucket .
3. Sort within buckets — sort each bucket using any algorithm (typically insertion sort, which is fast on small arrays).
4. Concatenate — concatenate all sorted buckets to form the final result.

Why uniform distribution matters: With uniformly distributed data, each bucket expects to contain elements on average. Thus, sorting each bucket is fast.

1.4.2 Complexity Analysis

Setup: Let = number of elements in bucket .

Total time:

where is for initialization and distribution, and is for sorting bucket with insertion sort.

Expected running time (with uniform distribution):

Each element independently falls into each bucket with probability . Thus, follows a binomial distribution with parameters and , giving:

Therefore:

Why do we choose buckets? If we choose too few buckets, they’ll be crowded and sorting will be slow. If we choose too many, initializing empty buckets is wasteful. With buckets for elements, we achieve the sweet spot where expected bucket size is and expected total time is .

1.4.3 Worst Case

If all elements are in a single bucket, we resort to insertion sort on all elements:

This can happen if the data is not actually uniformly distributed or if there are pathological cases.

1.5 Comparison of Linear-Time Sorting Algorithms

All three linear-time algorithms have advantages and disadvantages:

Algorithm	Time	Space	Assumption	Stable	Notes
Counting Sort			Small integer range	Yes	Practical when
Radix Sort			Multi-digit numbers	Yes (with stable sub-sort)	Effective for large integers/strings
Bucket Sort	average		Uniformly distributed in range	Yes	Can be worst case

Choosing the right algorithm:

• Use Counting Sort when elements are small integers in a known narrow range (e.g., sorting grades 0-100, or counting digit frequencies).
• Use Radix Sort when elements are multi-digit numbers (especially for binary or fixed-width representations). It’s practical for sorting strings with fixed alphabet size.
• Use Bucket Sort when data is known to be uniformly distributed and you want simple, practical average-case linear time.
• Use comparison-based sorts ( like merge sort or quicksort) when you need worst-case guarantees or when the assumptions of linear-time algorithms don’t hold.

---

2. Definitions

• Comparison-Based Sorting: A sorting algorithm that makes all decisions based on comparing pairs of elements, such as comparing .
• Decision Tree: A binary tree model representing the execution of a comparison-based sorting algorithm, where internal nodes are comparisons and leaves are sorted permutations.
• Lower Bound: A proven minimum number of operations (e.g., comparisons) that any algorithm of a certain class must perform.
• Counting Sort: A linear-time sorting algorithm for integers in a small range that counts occurrences of each value.
• Stable Sort: A sorting algorithm that preserves the relative order of elements with equal keys.
• Cumulative Count Array: In counting sort, the array that stores the number of elements less than or equal to each value, used to determine final positions.
• Radix Sort: A linear-time sorting algorithm that sorts multi-digit numbers by sorting each digit position independently, starting from the least significant digit.
• Digit (Radix Sort): A single digit in a particular position of a multi-digit number, treated as the sorting key for a single pass.
• Least Significant Digit (LSD): The rightmost digit in a number; sorting by LSD first is standard in radix sort.
• Bucket Sort: A linear-time sorting algorithm for uniformly distributed values that partitions the range into equal-sized buckets, sorts each bucket, and concatenates.
• Bucket: A subdivision of the value range in bucket sort, into which elements are distributed before individual sorting.
• Uniform Distribution: A probability distribution where each value in a range is equally likely; the assumption required for bucket sort’s average-case analysis.
• Amortized Analysis: Analysis showing that over a sequence of operations, the average cost per operation is low, even if some operations are expensive.
• In-Place Sorting: A sorting algorithm that requires only or extra space, not counting the input and output.
• Linear-Time Sorting: An algorithm that runs in or time, achieving the theoretical limit when applicable.

---

3. Formulas

• Lower Bound (Decision Tree):
• Lower Bound Derivation:
• Counting Sort Time Complexity: where is the number of elements and is the range of values
• Counting Sort Space Complexity: for output and count arrays
• Radix Sort Time Complexity (General): where is the number of digits and is the base
• Radix Sort Time Complexity (Binary): where is the number of bits
• Radix Sort with Optimized Radix: where is the bits per digit; optimal at
• Bucket Index Formula: for element
• Bucket Sort Time Complexity (Average): with uniform distribution
• Bucket Sort Time Complexity (Worst): when all elements fall in one bucket
• Expected Bucket Size (Uniform Distribution): for elements in buckets
• Expected Cost of Sorting Bucket (Insertion Sort): for bucket

---

4. Practice

4.1. Apply Counting Sort (Problem Set 4, Task 1)

Apply counting sort to the array with keys and associated data:

Keys | 3 | 1 | 6 | 3 | 0 | 3 | 6 | 3 | 1 | 4 | 6 | 4 | 6 |
Data | A | O | S | R | Y | E | O | A | U | W | M | E | E |

Show: 1. The auxiliary array before filling the output 2. The auxiliary array after the algorithm finishes 3. The final output array with keys and data

Click to see the solution

Key Concept: Use counting sort with stability to preserve the relative order of equal keys.

Input: Keys , Data

Range: to (so )

Step 1: Count Frequencies

Value | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Count | 1 | 2 | 0 | 4 | 2 | 0 | 4 |

This gives us array before filling output:

Step 2: Cumulative Counts

Value | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Cumulative | 1 | 3 | 3 | 7 | 9 | 9 | 13 |

This array after the algorithm finishes (before element placement):

(This represents the ending position of each group in the output.)

Step 3: Backward Traversal to Place Elements

Traverse input from right to left. For each element at position :

• Get key
• Place at position in output
• Decrement

Step		Key	Data		Output Position	Updated
1	12	6	E	13	13
2	11	4	E	9	9
3	10	6	M	12	12
4	9	4	W	8	8
5	8	1	U	3	3
6	7	3	A	7	7
7	6	6	O	11	11
8	5	3	E	6	6
9	4	0	Y	1	1
10	3	3	R	5	5
11	2	6	S	10	10
12	1	1	O	2	2
13	0	3	A	4	4

Final Output Array with Keys and Data (sorted by key):

Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
Key | 0 | 1 | 1 | 3 | 3 | 3 | 3 | 4 | 4 | 6 | 6 | 6 | 6 |
Data | Y | O | U | A | R | E | A | W | E | S | O | M | E |

Answer: 1. Auxiliary array before filling: (frequency counts) 2. Auxiliary array after algorithm finishes: (cumulative counts after decrementing) 3. Output array: Keys in sorted order with corresponding data (stable)

4.2. Radix Sort Complexity for Programs (Problem Set 4, Task 2)

Consider a hierarchical structure of programs:

• Each program is a sequence of at most code blocks
• Each code block is a sequence of at most instruction codes
• Each instruction code is an element of an instruction set of size

Estimate the worst-case time complexity of the Radix Sort algorithm on an array of programs when code blocks are sorted using:

(a) Insertion Sort (b) Merge Sort (c) Radix Sort (with Counting Sort for instruction codes)

Provide justification for each complexity in terms of , , , and . (Important: Comparing instruction codes takes time, but comparing code blocks or programs is NOT .)

Click to see the solution

Key Concept: Analyze radix sort where we sort by code blocks (not individual instructions). The cost of comparing code blocks depends on how we sort them.

(a) Code blocks sorted using Insertion Sort:

1. Structure: Radix sort makes passes over programs, sorting by each code block position
2. Cost per pass: Each pass uses insertion sort to order code blocks. Insertion sort does comparisons in worst case, and each comparison takes (comparing two code blocks of length )
3. Cost of one pass:
4. Total: passes × per pass

Justification: Each of passes uses insertion sort ( comparisons), and each comparison between code blocks takes time.

(b) Code blocks sorted using Merge Sort:

1. Cost per pass: Merge sort makes comparisons, each taking
2. Cost of one pass:
3. Total: passes ×

Justification: Each of passes uses merge sort ( comparisons), and each comparison takes time.

(c) Code blocks sorted using Radix Sort (with Counting Sort for instructions):

1. Structure: Radix sort makes passes over programs. Each pass sorts by one code block, which itself is sorted by instruction codes using counting sort.
2. Cost of sorting one code block (using radix sort with digits and alphabet size ):
   • passes of counting sort
   • Each pass: to count and place elements
   • Cost per code block:
3. Cost of one outer pass: Sorting programs by one code block position takes
4. Total: outer passes ×

Justification: The outer radix sort makes passes. Each pass sorts code blocks using radix sort with digits and alphabet size , which takes .

Summary Comparison:

Method	Complexity
(a) Insertion Sort
(b) Merge Sort
(c) Radix Sort

For large , method (c) is superior when is not too large. Method (b) is better than (a) for large , but (a) may be faster for very small and .

4.3. Decision Tree for Quicksort Variation (Problem Set 4, Task 3)

Construct a decision tree for a variation of Quick-Sort where the pivot is always the second element of the subarray, for an input array of size 4. Answer the following:

1. How many leaves are there in the decision tree?
2. What is the length of the shortest path from the root to a leaf?
3. What is the length of the longest path from the root to a leaf?

Click to see the solution

Key Concept: A decision tree for quicksort shows all possible comparison outcomes when partitioning. With the second element as pivot, the tree structure differs from standard quicksort.

(a) Number of leaves:

A decision tree for any sorting algorithm on elements must have at least leaves (one per distinct permutation). For :

Each leaf represents a final sorted permutation of the four elements.

(b) Length of shortest path:

The shortest path occurs when the pivot choices are optimal, dividing the array nearly evenly at each step, requiring fewer comparisons.

Analysis:

• First partition: Using the 2nd element as pivot on 4 elements requires comparisons to partition into groups
• Best case (balanced partitions):
  • Level 0 (root): 1 problem of size 4
  • Level 1: 2 subproblems (sizes 1-2 each) — 1 comparison (pivot placement)
  • Level 2: Remaining elements — 0-1 comparisons (some may be size 1)

Optimal path example:

• Root: Compare elements to place 2nd element → 3 comparisons minimum to fully partition
• If we get lucky with first partition (elements before pivot, pivot itself, elements after pivot), size 1:

More careful analysis using decision tree height lower bound:

So the minimum height is comparisons.

However, the shortest path (not requiring all leaves to be reached) can be shorter. If we find a sorted arrangement quickly, we may need as few as:

For 4 elements with 2nd element as pivot, in the best case scenario:

• Partition step: 3 comparisons to partition all elements around the 2nd element
• Worst case for subsequent levels: additional comparisons

But we must reach a leaf (valid permutation). The shortest actual path is around 5-6 comparisons in the worst case scenario.

Answer: Shortest path length = 5 (based on lower bound )

(c) Length of longest path:

The longest path occurs when the pivot choices create highly unbalanced partitions (one partition has 0 elements, the other has 3).

Worst-case scenario:

• First partition: 2nd element is the smallest or largest
  • Elements before pivot: 0 (or 3)
  • Elements after pivot: 3 (or 0)
  • Comparisons: 3
• Second partition: Pivot is again smallest/largest in remaining 3 elements
  • Creates subproblem of size 2
  • Comparisons: 2
• Third partition: Remaining 2 elements
  • Comparisons: 1

Total comparisons in worst case:

But we need to count the full decision path. The longest path continues until we have all elements sorted (reach a leaf). With elements and unbalanced partitions:

This matches the worst-case recurrence for quicksort: in the worst case, which gives us 6 total comparisons for .

Answer: Longest path length = 6

Summary:

Property	Value
(a) Number of leaves
(b) Shortest path length	5
(c) Longest path length	6

Interpretation:

• The tree must have 24 leaves (all permutations)
• Best case: comparisons to reach some leaf
• Worst case: 6 comparisons when the pivot choices create unbalanced partitions

4.4. Prove Lower Bound for Comparison-Based Sorting (Lecture 4, Example 1)

Prove that any comparison-based sorting algorithm requires at least comparisons in the worst case.

Click to see the solution

Key Concept: Use the decision tree model. A decision tree has at least leaves (one for each permutation), and the height of the tree is the worst-case number of comparisons.

1. Setup Decision Tree:

   • For any sorting algorithm on input of size , we can model its execution as a binary decision tree.
   • Each internal node represents a comparison operation.
   • Each leaf represents a final sorted order (one of the possible permutations).
   • The path from root to leaf represents the sequence of comparisons for a particular input.

2. Count Leaves:

   • There must be at least distinct leaves because there are possible input permutations.
   • Different input permutations might lead to the same sorted order, but we need at least one leaf per distinct permutation.

3. Relate Leaves to Height:

   • A complete binary tree of height has exactly leaves.
   • Therefore:
   • Taking logarithms:

4. Lower Bound on :

   To find a lower bound, keep only terms from to :

   Simplify:

   This is because the first term dominates.

5. Conclusion:

Answer: Any comparison-based sorting algorithm requires at least comparisons in the worst case, proven via the decision tree lower bound.

4.5. Apply Radix Sort to Decimal Numbers (Lecture 4, Example 2)

Sort the array using radix sort. Show the state after sorting by each digit.

Click to see the solution

Key Concept: Sort by each digit position from least to most significant, using a stable sort (like counting sort) at each step.

Input: (3-digit numbers, each digit in )

Pass 1: Sort by Units Digit (Least Significant)

Elements grouped by units digit (using stable sort):

• 0: 720
• 5: 355
• 6: 436
• 7: 457, 657 (stable: 457 comes before 657 since it appeared first)
• 9: 329, 839 (stable: 329 comes before 839)

Result after Pass 1:

Pass 2: Sort by Tens Digit (Stable)

Current array:

Elements grouped by tens digit:

• 2: 720, 329 (stable order preserved from previous pass)
• 3: 436, 839
• 5: 355, 457, 657 (stable order preserved)

Result after Pass 2:

Pass 3: Sort by Hundreds Digit (Most Significant, Stable)

Current array:

Elements grouped by hundreds digit:

• 3: 329, 355 (stable order preserved)
• 4: 436, 457 (stable order preserved)
• 6: 657
• 7: 720
• 8: 839

Result after Pass 3:

Final Sorted Array: ✓

Complexity Analysis:

• elements
• digits
• possible values per digit (0-9)
• Time: ✓

Answer: After sorting by units, tens, and hundreds digits respectively, the array becomes fully sorted: .

4.6. Analyze Bucket Sort Average Case (Lecture 4, Example 3)

Analyze the average-case time complexity of bucket sort for elements uniformly distributed in using buckets and insertion sort within buckets.

Click to see the solution

Key Concept: With uniform distribution and buckets, the expected size of each bucket is , making insertion sort fast on average.

1. Setup:
   • elements, uniformly distributed in
   • buckets, each covering an interval of width
   • Bucket covers
   • Each element independently falls into bucket with probability
2. Distribution of Bucket Sizes:
   • Let be the size of bucket (number of elements in it)
   • Each element independently falls into bucket with probability
   • follows a binomial distribution:
3. Expected Bucket Size:
4. Expected Cost of Sorting Bucket :
   • We use insertion sort, which takes worst-case time
   • But we care about expected time:
   • For a binomial distribution:
5. Total Expected Time:
6. Why buckets is optimal:
   • With buckets and elements: expected bucket size is
   • Insertion sort on each bucket costs
   • Total:
   • This is minimized when , giving total time

Answer: Average-case time complexity is with buckets. The key insight is that each bucket is expected to have size with uniform distribution, making insertion sort efficient.

4.7. Decision Tree for Sorting Three Elements (Lecture 4, Example 4)

Construct a decision tree for insertion sort when sorting three elements . Identify all leaves (sorted permutations).

Click to see the solution

Key Concept: A decision tree shows all possible comparisons and outcomes. Each internal node represents a comparison; leaves represent final sorted orders.

Input: Three elements , , (unlabeled — we don’t know their values)

Insertion Sort Logic: 1. Compare and 2. Based on the outcome, determine where to insert

Decision Tree:

Root: Compare and

• Left branch (): We know .
  • Next: Compare and
    • Left branch (): We have . Leaf:
    • Right branch (): We have and . Now compare and :
      • Left branch (): We have . Leaf:
      • Right branch (): We have . Leaf:
• Right branch (): We know .
  • Next: Compare and
    • Left branch (): We have . Leaf:
    • Right branch (): We have and . Now compare and :
      • Left branch (): We have . Leaf:
      • Right branch (): We have . Leaf:

Complete Decision Tree:

                        a ≤ b?
                       /      \
                     YES       NO
                     /          \
                 b ≤ c?        a ≤ c?
                 /    \         /    \
               YES    NO      YES    NO
               /       \      /       \
           a≤b≤c    a≤c?  b<a≤c    b≤c?
                    /   \           /   \
               a≤c<b  c<a≤b     b≤c<a  c<b<a

The six leaves correspond to the six permutations of three elements:

Complete list of leaves (sorted orders):

Leaf	Permutation	Path
1		YES, YES
2		YES, NO, YES
3		YES, NO, NO
4		NO, YES
5		NO, NO, YES
6		NO, NO, NO

Height of tree: Longest path has 3 comparisons (e.g., path to Leaf 2). Since , any decision tree for sorting 3 elements requires at least comparisons in the worst case.

Answer: The decision tree has 6 leaves (one per permutation of three elements), root represents , and the longest path from root to leaf requires 3 comparisons, corresponding to the worst-case lower bound.

4.8. Stability of Radix Sort (Lecture 4, Example 5)

Explain why radix sort is stable when the sub-sorting algorithm (used for each digit) is stable. Provide an example.

Click to see the solution

Key Concept: Stability is preserved if the sub-sort is stable. We sort from least significant to most significant digit; stability at each step maintains the correct order from prior steps.

Claim: If the sub-sorting algorithm is stable, then radix sort is stable.

Proof:

Suppose we are sorting records with multi-digit keys. After sorting by the last digits, records are in the correct order with respect to those digits. When we sort by digit :

• Records with the same digit value will be reordered by the stable sub-sort
• Since the sub-sort is stable, records that are already in the correct relative order (from prior sorting by digits ) will remain in that order
• Thus, records are now sorted correctly by digits

By induction, after processing all digits, the records are sorted.

Example:

Consider pairs (key, data) where keys are 2-digit numbers:

Input:

Pass 1: Sort by units digit (least significant)

Using stable counting sort on the units digit:

Units Digit	Records
2
3
5

After Pass 1 (sorted by units digit, stable within ties):

Note: comes before because B appeared before E in the original array (stability).

Pass 2: Sort by tens digit (most significant)

Using stable counting sort on the tens digit:

Tens Digit	Records (in their current order from Pass 1)
1
2

After Pass 2 (sorted by tens digit, then units digit):

Note:

• Within tens digit 1: and maintain their order from Pass 1 (same units digit 2, so they remain in relative order by stability). The sub-sort doesn’t change their relative order because they have the same tens digit value.
• Within tens digit 2: comes before because A appeared before C in the original array, and the sub-sort preserves this (stability).

Final sorted result: ✓

The keys are in order: 12, 12, 15, 23, 23. For equal keys (12, 12) and (23, 23), the original order is preserved (B before E, A before C).

Answer: Radix sort is stable because stable sub-sorting at each digit preserves the relative order of elements that are equal in the current digit, which maintains the correct order from previous digits. The cumulative effect ensures that after all passes, the entire multi-digit keys are in correct sorted order with stability preserved.

4.9. Compare Sorting Algorithms on Different Data (Lecture 4, Task 1)

For each scenario below, recommend the best sorting algorithm and justify your choice:

1. Sorting 1 million English words of varying length
2. Sorting 1 billion 32-bit unsigned integers
3. Sorting 100 students by grade (0-100)
4. Sorting a linked list of arbitrary integers

Click to see the solution

Key Concept: Different algorithms excel in different scenarios. Consider the input size, range, data distribution, and memory constraints.

(1) Sorting 1 million English words of varying length:

Recommendation: Merge sort or quicksort (comparison-based)

Justification:

• Words are complex objects; no obvious numeric range
• Variable length makes radix sort awkward (would need to pad all words to max length)
• English words are not uniformly distributed (bucket sort would be inefficient)
• comparisons is acceptable
• Merge sort guarantees even in worst case
• Quick sort is faster in practice with good pivot selection

(2) Sorting 1 billion 32-bit unsigned integers:

Recommendation: Radix sort (with 8-bit or 16-bit radix)

Justification:

• Integers have a fixed, small range:
• Radix sort with 8-bit chunks: ,
• Time: — linear!
• Counting sort (radix sort with 8-bit chunks) is per pass
• Much faster than for merge/quick sort

(3) Sorting 100 students by grade (0-100):

Recommendation: Counting sort

Justification:

• Small range: grades are integers in
• ,
• Time: — extremely fast
• Far better than for comparison-based sorts
• Simple to implement
• Can easily handle ties (use stable counting sort)

(4) Sorting a linked list of arbitrary integers:

Recommendation: Merge sort

Justification:

• Linked lists don’t support fast random access
• Radix/bucket sort need to iterate over array indices — inefficient on linked lists
• Merge sort is naturally suited to linked lists: can merge two lists by only following pointers, no array indexing needed
• Insertion sort on linked lists is (slow traversal for each insertion)
• Quicksort on linked lists is awkward (hard to partition without random access)
• Merge sort: , naturally fits linked list structure

Answer: 1. English words: Merge sort or quicksort 2. Integers (32-bit): Radix sort 3. Grades (0-100): Counting sort 4. Linked list: Merge sort

4.10. Estimate Complexity of Radix Sort with Arbitrary Radix (Lecture 4, Task 2)

Show that we can sort numbers in the range in time. What radix and number of digits should we use?

Click to see the solution

Key Concept: Use radix sort with base and digits.

1. Problem Setup:
   • Range:
   • We need to express numbers in a suitable base- representation
2. Choose Radix and Digits:
   • Let radix (each digit is in range )
   • To represent numbers up to in base : we need digits where
   • Thus digits
   Example: If , numbers are represented as 5-digit numbers in base 10: 00000 to 99999.
3. Radix Sort Complexity:
   • With digits and radix :
   • Time per pass (using counting sort):
   • Total passes:
   • Total time: ✓
4. Verification:
   • For : Sort numbers in in time ✓
   • For : Sort numbers in in time ✓

Answer: Use radix sort with base and digits. Each pass takes , and we perform 5 passes, for a total of .

4.11. Time Complexity of Radix Sort with Variable-Radix (Lecture 4, Task 3)

Show that we can sort -bit numbers in for any . What choice of minimizes the time complexity?

Click to see the solution

Key Concept: Instead of sorting by each bit individually (radix 2), we can process multiple bits at once (radix ).

1. Setup:
   • Numbers are represented in binary with bits total
   • Instead of processing 1 bit at a time, process bits at once
   • This creates a base- representation with digits (each digit is bits)
2. Number of Passes:
   • If we process bits per pass, we need passes
3. Time per Pass:
   • Each pass counts elements based on an -bit value (range )
   • Using counting sort: per pass
4. Total Time:
5. Optimization — Find Minimum:
   • We want to minimize
   • Take derivative:
   • Setting to zero and solving: the optimal satisfies , so
6. Optimal Choice:
   • : Process 1 bit at a time.
   • : (if )
   • : Process all bits at once. — only if is manageable
   • : (if )
7. Practical Recommendation:
   • If is very large, choose to balance the two terms
   • This achieves close-to-linear time when

Answer: Radix sort with -bit digits requires time. The optimal choice is (if ), which minimizes the expression by balancing the number of passes and the cost per pass.

4.12. Range Queries Using Counting Sort (Lecture 4, Task 4)

Preprocess an array of numbers in range using counting sort so that queries “how many elements in range ?” can be answered in time.

Click to see the solution

Key Concept: After counting sort, build a prefix sum array. Range queries become simple subtractions.

1. Preprocessing:

   • Perform counting sort to get the count array where = count of elements equal to
   • Compute cumulative sum:
   • Now = total count of elements (or )

2. Range Query [a, b]:

   • To count elements in range (inclusive):
   • This is time!

3. Explanation:

   • = number of elements
   • = number of elements = number of elements
   • Difference = number of elements in

4. Example:

   Input array:

   Step 1: Count frequencies

   • (four 0s, two 1s, zero 2s, two 3s)

   Step 2: Cumulative sum

   • (four elements )
   • (six elements )
   • (six elements )
   • (eight elements )
   • Result:

   Query: How many elements in range [1, 3]? Elements in : — count is 4 ✓

   Query: How many elements in range [0, 1]? But is out of bounds. Instead, if querying : So: ✓ (Elements 0, 0, 0, 0, 1, 1)

5. Time complexity:

   • Preprocessing (counting sort):
   • Each query:
   • Total for queries:

Answer: Build a cumulative count array using counting sort. To answer “how many in range ?”, return in time. Preprocessing takes .